Search results for " Parikh vectors"

showing 3 items of 3 documents

On a class of languages with holonomic generating functions

2017

We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM

Class (set theory)Holonomic functionsGeneral Computer Science0102 computer and information sciences02 engineering and technologyContext free language01 natural sciencesTheoretical Computer ScienceMorphismRegular language0202 electrical engineering electronic engineering information engineeringParikh vectorMathematicsDiscrete mathematicsk-counter machineHolonomic functionConjecturek-counter machinesSettore INF/01 - InformaticaHolonomicParikh automataComputer Science (all)Context-free languageParikh vectorsAlgebraContext free languagesClosure (mathematics)010201 computation theory & mathematicsBounded function020201 artificial intelligence & image processingHolonomic functions; Parikh vectors; Context free languages; k-counter machines; Parikh automata
researchProduct

Searching for Jumbled Patterns in Strings

2009

Parikh vectors permuted strings pattern matching string algorithms average case analysisString algorithmsAverage case analysis; Parikh vectors; Pattern matching; Permuted strings; String algorithmsPermuted stringsParikh vectorsAverage case analysisPattern matching
researchProduct

On Approximate Jumbled Pattern Matching in Strings

2011

Given a string s, the Parikh vector of s, denoted p(s), counts the multiplicity of each character in s. Searching for a match of a Parikh vector q in the text s requires finding a substring t of s with p(t) = q. This can be viewed as the task of finding a jumbled (permuted) version of a query pattern, hence the term Jumbled Pattern Matching. We present several algorithms for the approximate version of the problem: Given a string s and two Parikh vectors u, v (the query bounds), find all maximal occurrences in s of some Parikh vector q such that u <= q <= v. This definition encompasses several natural versions of approximate Parikh vector search. We present an algorithm solving this problem …

Parikh vectors: Average case analysiApproximate searchString algorithmsDiscrete mathematicsWeight functionanalysisSearch engine indexingParikh vectorsAverage case analysisApproximate string matchingSubstringString algorithmTheoretical Computer ScienceCombinatoricsComputational Theory and MathematicsString algorithms Pattern matching Parikh vectors Average case analysis Approximate search Permuted stringsPermuted stringsAverage caseTheory of computationWavelet TreePreprocessorPattern matchingPattern matchingMathematicsTheory of Computing Systems
researchProduct